import java.util.HashMap;
import java.util.Map;

/**
 * @Author: linzp
 * @Date: 2022/07/11/9:49
 */
public class demo0711 {
    public static void main(String[] args) {

    }

    /**
     * 76. 最小覆盖子串
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     * <p>
     * <p>
     * <p>
     * 注意：
     * <p>
     * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：s = "ADOBECODEBANC", t = "ABC"
     * 输出："BANC"
     * 示例 2：
     * <p>
     * 输入：s = "a", t = "a"
     * 输出："a"
     * 示例 3:
     * <p>
     * 输入: s = "a", t = "aa"
     * 输出: ""
     * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
     * 因此没有符合条件的子字符串，返回空字符串。
     * <p>
     * <p>
     * 提示：
     * <p>
     * 1 <= s.length, t.length <= 105
     * s 和 t 由英文字母组成
     * <p>
     * <p>
     * 进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
     */

    public String minWindow(String s, String t) {
//        ADOBECODEBANC
        if (s == null || s.length() == 0 || t == null || t.length() == 0) {
            return "";
        }
        int[] need = new int[128];//记录需要的字符串 正数为需要 负数为不需要（多余的）用于后期维护数组
        for (char index : t.toCharArray()) {
            need[index]++;
        }
        int count = t.length();//需要t个字符串，等于=0时就可以维护数组了
        int size = Integer.MAX_VALUE;
        int l = 0, r = 0;
        int start = 0;//记录起始位置用于返回字符串
        while (r < s.length()) {
            char index = s.charAt(r);
            if (need[index] > 0) {
                need[index]--;
                count--;
            }else {
                need[index]--;//遍历过的都要--,是通过count和need的正负来收缩数组的。
            }
            if (count == 0) {//收集齐了，维护左边界
                while (l < r && need[s.charAt(l)] < 0) {
                    need[s.charAt(l)]++;//维护字典，不然有可能是-2，-3这些重复了的，要一个个消除回去的。
                    l++;
                }
                size = Math.min(size, r - l + 1);
                if (size== r - l + 1){
                    start = l;
                }
                need[s.charAt(l)]++;//维护下面收缩的左边界 要放前面不然l++了位置变了，
                l++;//收缩一位目标字符串
                count++;
            }
            r++;
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);

    }
}
